import java.util.ArrayList;
import java.util.List;
public class demo1 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>>list=new ArrayList<>();
        list.add(new Pair<TreeNode,Integer>(root,1));
        int max=0;
        while(!list.isEmpty()){
            Pair<TreeNode, Integer> t1=list.get(0);
            Pair<TreeNode,Integer>t2=list.get(list.size()-1);
            max= Math.max(max,t2.getValue()-t1.getValue()+1);
            List<Pair<TreeNode,Integer>>temp=new ArrayList<>();
            for(Pair<TreeNode,Integer> integerPair:list){
                TreeNode treeNode=integerPair.getKey();
                int s=integerPair.getValue();
                if(treeNode.left!=null){
                    temp.add(new Pair<TreeNode,Integer>(treeNode.left,s*2));
                }
                if(treeNode.right!=null)temp.add(new Pair<TreeNode,Integer>(treeNode.right,s*2+1));
            }
            list=temp;
        }
        return max;
    }
}
